/**
 * @brief
 * KMP 算法理解 https://blog.csdn.net/weixin_46007276
 * 
 */
/**
 * @file String.c
 * @author Monomania(13015159350@qq.com)
 * @brief 这是串的顺序结构，注意串的链式结构没有顺序结构来的好用
 * @version 0.1
 * @date 2021-08-30
 * @copyright Copyright (c) 2021
 * 
 */
#include "String.h"
#include <windows.h>
#include "stdio.h"    
#include "stdlib.h"  
#include "io.h"  
#include "math.h"  
#include "time.h"
// #define NDEBUG
#include "assert.h"
// #include <conio.h> //清除命令行

/**
 *  * 抽象数据类型

ADT  串（String）
Data
	串中元素仅由一个字符组成。相邻元素具有前驱和后继关系。
Operation
	StrAssign(T, *chars):   生成一个其值等于字符串常量chars的串T。
	StrCopy(T, S):          串S存在，由串S复制得到串T
	ClearString(S):         若串S存在，将串清空
    StringEmpty(S):         若串S为空，返回True，否则返回False
	StrLength(S):           返回串S的元素个数，即串的长度
    StrCompare(S, T):       若S>T，返回值>0, 若S=T，返回0，若S<T，返回值<0
    Concat(T, S1, S2):      用T返回由S1和S2连接而成的新串
	SubString(Sub, S, pos, len):若串S存在，1≦pos≦StrLength(S),
                                且 0≦len≦StrLength(S)-pos+1，用Sub返回串S的第pos个字符串起长度为len的字符串
	Index(S, T, pos):       若串S和T存在，T是非空串，1≦pos≦StrLength(S).
                            若主串S中存在串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置，否则返回0
	Replace(S, T, V):       串S、T和V存在，T是非空串。用V替换主串S中出现的所有与T相等的不重叠的字串
    StrInsert(S, pos, T):   串S和T存在，1≦pos≦StrLength(S)+1。
                            在串S的第pos个字符之前插入串T。
    StrDelete(S, pos, len): 串S存在，1≦pos≦StrLength(S)-len+1。
                            从串S中删除第pos个字符起长度为len的子串。
endADT
*/
/**
 * @使用说明 
 * 1. 将文件包含在工程文件中
 * 2. 根据需求，修改元素类型ElemType
 * 3. 根据需求修改visit()函数，自定义输出格式
 * 4. 修改INF的数值，确保为一个不可能存在的数
 * 
 * 注意
 * 强调是单链表时使用  LinkList
 * 强调是一个节点时使用 Node* 
 * 在参数列表中，如果有*（或者C++的&）表示要对原数据进行操作。————就算链表本来就是个指针，也要遵守这个准则!!
 */

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 50 /* 存储空间初始分配量 */

typedef int Status;		/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;	/* ElemType类型根据实际情况而定，这里假设为int */

typedef char String[MAXSIZE+1]; /*  0号单元存放串的长度 */


/**
 * @brief 生成一个其值等于字符串常量chars的串T。
 * 
 * @param T 
 * @param chars 
 * @return Status 
 */
Status StrAssign(String T,const char *chars)
{ 
	int i;
	memset(T,'\0', sizeof(*T));
	if(strlen(chars)>MAXSIZE)
		return ERROR;
	else
	{   //注意数组与数组之间不能 直接赋值
		for(i=0;chars[i]!='\0';i++)
			T[i]=*(chars+i);
        T[i] = '\0';
        return OK;
	}
}


/**
 * @brief 串S存在，由串S复制得到串T
 * 
 * @param T 
 * @param S 
 * @return Status 
 */
Status StrCopy(String T, String S)
{
	int i;
	memset(T,'\0', sizeof(*T));
	for(i=0;S[i]!='\0';i++)
		T[i]=S[i];
	T[i] = '\0';
	return OK;
}

/**
 * @brief 返回串S的元素个数，即串的长度
 * 
 * @param S 
 * @return int 
 */
int StrLength(String S)
{
	int i=0;
	for (i = 0; S[i] != '\0'; i++);
	return i;
}           

/**
 * @brief 清空字符串
 * 
 * @param S 
 * @return Status 
 */
Status ClearString(String S)
{
	memset(S,'\0', sizeof(*S));
	return OK;
}

/**
 * @brief 判断字符串是否为空
 * 
 * @param S 
 * @return Status 
 */
Status StringEmpty(String S)
{
	if (strlen(S)==0)
		return TRUE;
	return FALSE;

	// if (StrLength(S)==0)
	// 	return TRUE;
	// return FALSE;
}


/*  初始条件: 串S和T存在 */
/*  操作结果: 若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0 */
/**
 * @brief 
 * 
 * @param S 若S>T，返回值>0, 若S=T，返回0，若S<T，返回值<0
 * @param T 
 * @return int 
 */
int StrCompare(String S,String T)
{ 
	int i;
	for(i=0;S[i] != '\0' &&T[i] != '\0';i++)
		if(S[i]!=T[i])
			return S[i]-T[i];
	return StrLength(S)-StrLength(T);
}

/**
 * @brief 用T返回S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE
 * 
 * @param T 
 * @param S1 
 * @param S2 
 * @return Status 
 */
Status Concat(String T,String S1, String S2)
{
	int i = 0, j = 0;
	memset(T,'\0', sizeof(*T));  //先清空一下
	// 未截断
	if (strlen(S1)+strlen(S2) <= MAXSIZE)
	{
		// StrCopy(T, S1);
		for (i=0; S1[i] != '\0';i++)
		{
			T[i]=S1[i];
		}
		for (j=0; S2[j] != '\0';j++)
		{
			T[i+j]=S2[j];
		}
		T[i + j] = '\0';
		return TRUE;
	}
	else{
		// StrCopy(T, S1);
		for (i=0; S1[i] != '\0';i++)
		{
			T[i]=S1[i];
		}
		for (j=0; i + j != MAXSIZE;j++)
		{
			T[i+j]=S2[j];
		}
		T[MAXSIZE] = '\0';
		return FALSE;
	}
	
	return OK;
}


/**
 * @brief 用Sub返回串S的第pos个字符起长度为len的子串
 * 
 * @param Sub 
 * @param S 
 * @param pos 
 * @param len 
 * @return Status 
 */
Status SubString(String Sub,String S,int pos,int len)
{
	int i;
	memset(Sub,'\0', sizeof(*Sub));  //先清空一下
	if(pos<1||pos>strlen(S)||len<0||len>strlen(S)-pos+1)
		return ERROR;
	for(i=0;i<len;i++)
		Sub[i]=S[pos+i-1];
	Sub[i]='\0';
	return OK;
}

/* 朴素的模式匹配法 */
int Index(String S, String T, int pos) 
{
	int i = pos;	/* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
	int j = 0;				/* j用于子串T中当前位置下标值 */
	while (i <= StrLength(S) && j <= StrLength(T)) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
	{
		if (S[i] == T[j]) 	/* 两字母相等则继续 */
      	{
			++i;
         	++j; 
      	} 
      	else 				/* 指针后退重新开始匹配 */
      	{  
         	i = i-j+2;		/* i退回到上次匹配首位的下一位 */
         	j = 1; 			/* j退回到子串T的首位 */
      	}      
	}
	if (j > StrLength(T)) 
		return i-StrLength(T);
	else 
		return 0;
}

/******************************** KMP算法 ****************************/

/* 通过计算返回子串T的next数组。 */
void get_next(String T, int *next) 
{
	int i,j;
  	i=0;
  	j=-1;
  	next[0]=-1;
  	while (i<StrLength(T))  /* 表示串T的长度 */
 	{
    	if(j==-1 || T[i]== T[j]) 	/* T[i]表示后缀的单个字符，T[j]表示前缀的单个字符 */
		{
      		++i;  
			++j;  
			next[i] = j;
    	} 
		else 
			j= next[j];	/* 若字符不相同，则j值回溯 */
  	}
}

/* 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。 */
/*  T非空，1≤pos≤StrLength(S)。 */
int Index_KMP(String S, String T, int pos) 
{
	int i = pos;		/* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
	int j = 0;			/* j用于子串T中当前位置下标值 */
	int next[255];		/* 定义一next数组 */
	get_next(T, next);	/* 对串T作分析，得到next数组 */
	while (i <= StrLength(S) && j <= StrLength(T)) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
	{
		if (j==0 || S[i] == T[j]) 	/* 两字母相等则继续，与朴素算法增加了j=0判断 */
      	{
         	++i;
         	++j; 
      	} 
      	else 			/* 指针后退重新开始匹配 */
      	 	j = next[j];/* j退回合适的位置，i值不变 */
	}
	if (j > StrLength(T)) 
		return i-StrLength(T);
	else 
		return 0;
}
/****************************************************************/

/******************************** 改进的KMP算法 ****************************/
/* 求模式串T的next函数修正值并存入数组nextval */
void get_nextval(String T, int *nextval) 
{
  	int i,j;
  	i=0;
  	j=-1;
  	nextval[0]=-1;
  	while (i<StrLength(T))  /* 此处T[0]表示串T的长度 */
 	{
    	if(j==-1 || T[i]== T[j]) 	/* T[i]表示后缀的单个字符，T[j]表示前缀的单个字符 */
		{
      		++i;  
			++j;  
			if (T[i]!=T[j])      /* 若当前字符与前缀字符不同 */
				nextval[i] = j;	/* 则当前的j为nextval在i位置的值 */
      		else 
				nextval[i] = nextval[j];	/* 如果与前缀字符相同，则将前缀字符的 */
											/* nextval值赋值给nextval在i位置的值 */
    	} 
		else 
			j= nextval[j];			/* 若字符不相同，则j值回溯 */
  	}
}

int Index_KMP1(String S, String T, int pos) 
{
	int i = pos;		/* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
	int j = 0;			/* j用于子串T中当前位置下标值 */
	int next[255];		/* 定义一next数组 */
	get_nextval(T, next);	/* 对串T作分析，得到next数组 */
	while (i <= StrLength(S) && j <= StrLength(T)) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
	{
		if (j==0 || S[i] == T[j]) 	/* 两字母相等则继续，与朴素算法增加了j=0判断 */
      	{
         	++i;
         	++j; 
      	} 
      	else 			/* 指针后退重新开始匹配 */
      	 	j = next[j];/* j退回合适的位置，i值不变 */
	}
	if (j > StrLength(T)) 
		return i-StrLength(T);
	else 
		return 0;
}

// SubString(Sub, S, pos, len):若串S存在，1≦pos≦StrLength(S),
//                             且 0≦len≦StrLength(S)-pos+1，用Sub返回串S的第pos个字符串起长度为len的字符串


// Replace(S, T, V):       串S、T和V存在，T是非空串。用V替换主串S中出现的所有与T相等的不重叠的字串
// StrInsert(S, pos, T):   串S和T存在，1≦pos≦StrLength(S)+1。
//                         在串S的第pos个字符之前插入串T。
// StrDelete(S, pos, len): 串S存在，1≦pos≦StrLength(S)-len+1。
//                         从串S中删除第pos个字符起长度为len的子串。


void showMenu(const char* tips)
{
    printf("================================================================\n");
    printf("\t\t\t %s \t\t\t\t\n", tips);
    printf("----------------------------------------------------------------\n");
    return;
}

int main(int argc, char** argv)
{
	String str1, str2, tmp;
	memset(str1,'\0', sizeof(*str1));
	memset(str2,'\0', sizeof(*str2));
	memset(tmp,'\0', sizeof(*tmp));

	system("cls");//清除命令行
	// clrscr();//清除命令行
	Sleep(500);
	/****************************************************************/
	showMenu("初始化生成字符串");
	StrAssign(str1, "Hello World!");
	printf("生成的字符串str1为：%s\r\n", str1);
	printf("字符串str1长度为(库函数)：%d\r\n", strlen(str1));
	printf("字符串str1长度为(自实现)：%d\r\n", StrLength(str1));
	/****************************************************************/
	showMenu("复制字符串");
	printf("复制前的字符串str2为：%s\r\n", str2);
	printf("复制前字符串str2长度为(库函数)：%d\r\n", strlen(str2));
	printf("复制前字符串str2长度为(自实现)：%d\r\n", StrLength(str2));
	StrCopy(str2, str1);
	printf("复制str1后的字符串str2为：%s\r\n", str2);
	printf("复制后字符串str2长度为(库函数)：%d\r\n", strlen(str2));
	printf("复制后字符串str2长度为(自实现)：%d\r\n", StrLength(str2));

	/****************************************************************/
	showMenu("清空字符串");
	ClearString(str2);
	printf("清空str2后的字符串：%s\r\n", str2);
	if (StringEmpty(str2))
		printf("字符串已被清空\r\n");
	/****************************************************************/
	showMenu("字符串比较");
	printf("%d\r\n", StrCompare(str1, str2));

	/****************************************************************/
	showMenu("字符串连接");
	StrAssign(str2, "0CJK0000");
	printf("连接前str1: %s, str2: %s\r\n", str1, str2);
	Concat(tmp, str1, str2);
	printf("连接后tmp: %s\r\n", tmp);

	/****************************************************************/
	showMenu("子串");
	SubString(tmp, str1, 2, 3);
	printf("父字符串str1为：%s\r\n", str1);
	printf("子字符串tmp为：%s\r\n", tmp);

    /****************************************************************/
	showMenu("KMP模式匹配");
    StrAssign(str1,"abcdababcdabd");
    printf("主串为str1为：%s\r\n", str1);
	StrAssign(str2,"abcdabd");
	printf("只串为str2为：%s\r\n", str2);
	printf("主串和子串在第%d个字符处首次匹配（朴素模式匹配算法）\n",Index(str1,str2,0));
	printf("主串和子串在第%d个字符处首次匹配（KMP算法） \n",Index_KMP(str1,str2,0));
	printf("主串和子串在第%d个字符处首次匹配（KMP改良算法） \n",Index_KMP1(str1,str2,0));

	return 0;
}